/*
 * @Author: wwssaabb
 * @Date: 2021-11-27 15:51:15
 * @LastEditTime: 2021-11-27 17:18:40
 * @FilePath: \handwritten-code\algorithm\最长回文子串.js
 */

/* 
给你一个字符串 s， 找到 s 中最长的回文子串。

示例 1：

输入： s = "babad"
输出： "bab"
解释： "aba"
同样是符合题意的答案。
示例 2：

输入： s = "cbbd"
输出： "bb"
示例 3：

输入： s = "a"
输出： "a"
示例 4：

输入： s = "ac"
输出： "a"

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/longest-palindromic-substring
*/

console.time(1)

//暴力解法，超时，结果正确
/*var longestPalindrome = function (s) {
  function isValid(str) {
    return str.split('').reverse().join('') === str
  }
  if (isValid(s)) return s
  let res = s[0]
  for (let l = 2; l < s.length; l++) {
    for (let x = 0; x < s.length - l + 1; x++) {
      if (isValid(s.slice(x, x + l))) res = s.slice(x, x + l)
    }
  }
  return res
}*/

//中心扩散法
var longestPalindrome = function (s) {
  let len = s.length;
  if (len < 2) return s
  let res = ''
  for (let i = 0; i < s.length; i++) {
    diffusion(i, i)
    diffusion(i, i + 1)
  }

  function diffusion(m, n) {
    while (m >= 0 && n < len && s[m] === s[n]) {
      m--;
      n++
    }
    if (n - m - 1 > res.length) {
      res = s.slice(m + 1, n)
    }
  }
  return res
}

console.timeEnd(1)

console.log(longestPalindrome('aa')) //aa
console.log(longestPalindrome('babad')) //aba
console.log(longestPalindrome('kyyrjtdplseovzwjkykrjwhxquwxsfsorjiumvxjhjmgeueafubtonhlerrgsgohfosqssmizcuqryqomsipovhhodpfyudtusjhonlqabhxfahfcjqxyckycstcqwxvicwkjeuboerkmjshfgiglceycmycadpnvoeaurqatesivajoqdilynbcihnidbizwkuaoegmytopzdmvvoewvhebqzskseeubnretjgnmyjwwgcooytfojeuzcuyhsznbcaiqpwcyusyyywqmmvqzvvceylnuwcbxybhqpvjumzomnabrjgcfaabqmiotlfojnyuolostmtacbwmwlqdfkbfikusuqtupdwdrjwqmuudbcvtpieiwteqbeyfyqejglmxofdjksqmzeugwvuniaxdrunyunnqpbnfbgqemvamaxuhjbyzqmhalrprhnindrkbopwbwsjeqrmyqipnqvjqzpjalqyfvaavyhytetllzupxjwozdfpmjhjlrnitnjgapzrakcqahaqetwllaaiadalmxgvpawqpgecojxfvcgxsbrldktufdrogkogbltcezflyctklpqrjymqzyzmtlssnavzcquytcskcnjzzrytsvawkavzboncxlhqfiofuohehaygxidxsofhmhzygklliovnwqbwwiiyarxtoihvjkdrzqsnmhdtdlpckuayhtfyirnhkrhbrwkdymjrjklonyggqnxhfvtkqxoicakzsxmgczpwhpkzcntkcwhkdkxvfnjbvjjoumczjyvdgkfukfuldolqnauvoyhoheoqvpwoisniv')) //qahaq